﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
// 原题连接：https://leetcode.cn/problems/decode-string/
/*
题目描述：
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。


示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
 

提示：
1 <= s.length <= 30
s 由小写英文字母、数字和方括号 '[]' 组成
s 保证是一个 有效 的输入。
s 中所有整数的取值范围为 [1, 300] 
*/

// 开始解题
// 方法1——暴力+递归
// 先将栈实现一下
// 重定义数据类型
typedef char DataType;

// 定义栈结构
typedef struct stack {
    DataType* data;
    int top;
    int capacity;
} Stack;

// 栈的初始化
void StackInit(Stack* ps);

// 压栈
void StackPush(Stack* ps, DataType x);
// 弹栈
void StackPop(Stack* ps);
// 返回栈顶数据
DataType StackTop(Stack* ps);
// 返回栈的数据个数
int StackSize(Stack* ps);
// 判断栈是否为空
bool StackEmpty(Stack* ps);
// 栈的销毁
void DestroyStack(Stack* ps);

// 栈的初始化
void StackInit(Stack* ps) {
    assert(ps);
    ps->data = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

// 压栈
void StackPush(Stack* ps, DataType x) {
    assert(ps);
    // 检查是否需要增容
    if (ps->top == ps->capacity) {
        int newCapacity = ps->capacity == 0 ? 10 : ps->capacity * 2;
        DataType* temp = (DataType*)realloc(ps->data, newCapacity * sizeof(DataType));
        if (NULL == temp) {
            perror("ralloc fail!\n");
            exit(-1);
        }
        ps->data = temp;
        ps->capacity = newCapacity;
    }
    ps->data[ps->top] = x;
    ps->top++;
}

// 弹栈
void StackPop(Stack* ps) {
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}

// 返回栈顶数据
DataType StackTop(Stack* ps) {
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->data[ps->top - 1];
}

// 返回栈的数据个数
int StackSize(Stack* ps) {
    assert(ps);
    assert(ps->top >= 0);
    return ps->top;
}

// 判断栈是否为空
bool StackEmpty(Stack* ps) {
    assert(ps);
    return ps->top == 0;
}

// 栈的销毁
void DestroyStack(Stack* ps) {
    assert(ps);
    free(ps->data);
    ps->data = NULL;
    ps->top = 0;
    ps->capacity = 0;
}


void repCode(Stack* stack, char** cur) {
    char* start = NULL;
    int time = StackTop(stack) - '0';
    StackPop(stack);
    int i = 0;
    for (i = 0; i < time; i++) {
        start = *cur + 1;
        while (*start != ']') {
            if (*start == '[') {
                repCode(stack, &start);
            }
            if (*start != ']') {
                StackPush(stack, *start);
                start++;
            }
        }
    }
    *cur = start + 1;
}

char* decodeString(char* s) {
    if (NULL == s) {
        return NULL;
    }
    Stack strStack;
    StackInit(&strStack);
    int i = 0;

    char* cur = s;
    while (*cur != '\0') {
        if (*cur == '[') {
            repCode(&strStack, &cur);
        }
        else {
            StackPush(&strStack, *cur);
            cur++;
        }
    }
    int len = StackSize(&strStack);
    char* retStr = (char*)malloc((len + 1) * sizeof(char));
    if (NULL == retStr) {
        perror("malloc fail!\n");
        exit(-1);
    }
    retStr[len] = '\0';
    for (i = len - 1; i >= 0; i--) {
        retStr[i] = StackTop(&strStack);
        StackPop(&strStack);
    }
    DestroyStack(&strStack);  
    return retStr;
}


int main() {
    char str[] = "100[LeetCode]";
    printf("%s\n", decodeString(str));
    return 0;
}